package demo_leetcode_day;

/*
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class demo_20200814 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node21 = new TreeNode(2);
        TreeNode node22 = new TreeNode(2);
        TreeNode node31 = new TreeNode(3);
        TreeNode node32 = new TreeNode(3);
        TreeNode node41 = new TreeNode(4);
        TreeNode node42 = new TreeNode(4);
        node1.left = node21;
        node1.right = node22;
        node21.left = node31;
        node22.right = node32;
        node31.left = node41;
        node32.right = node42;


//        TreeNode node1 = new TreeNode(1);
//        TreeNode node2 = new TreeNode(2);
//        TreeNode node3 = new TreeNode(3);
//        node1.right = node2;
//        node2.right = node3;

        System.out.println(new Solution().isBalanced(node1));
    }
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    static class Solution {
        public boolean isBalanced(TreeNode root) {
            if (null == root) return true;
            return (Math.abs(find(root.left) - find(root.right)) < 2) && isBalanced(root.left) && isBalanced(root.right);
        }
        private int find(TreeNode root){
            Integer floor = 0;
            if(null == root) return floor;
            // 节点组
            List<TreeNode> currentList = new ArrayList<>();
            List<TreeNode> nextList = new ArrayList<>();

            currentList.add(root);
            while (!currentList.isEmpty()){
                for (int i = 0; i < currentList.size(); i++) {
                    if(null != currentList.get(i).left) nextList.add(currentList.get(i).left);
                    if(null != currentList.get(i).right) nextList.add(currentList.get(i).right);
                }
                currentList = nextList;
                nextList = new ArrayList<>();
                floor++;
            }
            return floor;
        }
    }
}
